⟸ Go Back ⟸

Exercise 10 (Homework 7).

(NP, P, 3SAT)

Are they in \mathsf{P}?

Prove that the following languages on undirected graphs are in \mathsf{NP}. Which ones of them are in \mathsf{P}?

1. Two coloring. \mathtt{2COL} = \{ G \mid graph G has a coloring with two colors\}, where a k-coloring of G is an assignment of a number in \{1,\dots,k\} to each vertex of G such that no adjacent vertices get the same number.
2. Three coloring. \mathtt{3COL} = \{ G \mid graph G has a coloring with three colors\}.
3. Hamiltonian path. \mathtt{HP} = \{ G \mid graph G has a Hamiltonian path\}, where a path is said to be Hamiltonian if it visits every vertex exactly once.
4. Connectivity. \mathtt{CONNECTED} =\{ G \mid graph G is a connected graph\}.